/*
 * @Author: dadadaXU 1413107032@qq.com
 * @Date: 2025-02-05 21:48:45
 * @LastEditors: dadadaXU 1413107032@qq.com
 * @LastEditTime: 2025-02-05 23:20:15
 * @FilePath: \LeetCode\40.组合总和-ii.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
/*
 * @lc app=leetcode.cn id=40 lang=cpp
 *
 * [40] 组合总和 II
 *
 * 方法1：根据子集树进行搜索
 * - 问题1：计算规模 1 <= candidates.length <= 100
 * - 问题2：子集如何去重？
 */

#include <vector>
#include <algorithm>
#include <iostream>

// @lc code=start
class Solution
{
public:
    std::vector<std::vector<int>> result;
    std::vector<int> selected; // 记录选择数字
    int sum = 0;               // 组合总和
    int remain = 0;            // 未选择的数字之和
    int len = 0;               // candidates.length
    int m_target = 0;

    void visitSubTree(const std::vector<int> &candidates, int i)
    {
        if (i == len)
        {
            if (sum == m_target)
                result.push_back(selected);
            return;
        }
        int current = candidates[i];

        remain -= current; // 处理当前结点
        /* 左子树 剪枝看过去 */
        if (sum + current <= m_target) // 剪左树枝
        {
            sum += current;
            selected.push_back(current);
            visitSubTree(candidates, i + 1);
            sum -= current;
            selected.pop_back();
            /* 重复结点只访问第一个 */
            while (i + 1 < len && candidates[i] == candidates[i + 1])
                i++;
        }
        /* 右子树 剪枝看未来 */
        if (sum + remain >= m_target) // 剪右树枝
        {
            visitSubTree(candidates, i + 1);
        }
        remain += current; // 回溯父结点
    }

    std::vector<std::vector<int>> combinationSum2(std::vector<int> &candidates, int target)
    {
        std::sort(candidates.begin(), candidates.end());
        for (auto n : candidates)
            remain += n;

        len = candidates.size();
        m_target = target;

        visitSubTree(candidates, 0);

        return result;
    }
};
// @lc code=end

int main(void)
{
    Solution solution;
    std::vector<int> candidates = {1};

    std::vector<std::vector<int>> result = solution.combinationSum2(candidates, 1);
    for (auto v : result)
    {
        for (auto n : v)
            std::cout << n << " ";
        std::cout << std::endl;
    }

    return 0;
}